1. Field of the Invention
The present invention relates to electronic apparatus especially configured for computing fast Fourier transformations of such time-variable functions as electronic signals.
2. Discussion of the Prior Art
Rapid analysis of time-variable functions is important in many industry and military operations, such as in spectroscopy and SONAR. If the time-variable functions under consideration are simple harmonics of the form "a cos wt" or "b sin wt", the differential equations required for analyzing the functions, or determining system response thereto, can be quite easily and quickly solved.
However, not all commonly encountered time-variable functions, such as electronic signals or forces, are of such simple cosine or sine form, and analysis of these more complicated functions is thus more difficult and time consuming. Nevertheless, if, as is often possible, the function in question can be mathematically represented by an equivalent series summation of individual cosine and sine terms, the analysis can be greatly simplified, inasmuch as each cosine and sine term can be handled separately. Such equivalent representation or such transformation of complicated time-variable functions, f(t), when possible, is usually by the Fourier expansion: ##EQU1## or by one of the equivalent, summation or continuous integral forms. In the Fourier equation, f(t) is the time variable function to be transformed, and the coefficients a.sub.0, a.sub.1 . . . a.sub.n, b.sub.1 . . . b.sub.n are determined by the Euler formulas: ##EQU2## Integration of equations (2)-(4) is over an appropriate time interval, I, usually one period of the function f(t). Using equations (1)-(4), such commonly-encountered electronic signals as square waves or sawtooth waves can be represented by a series of cosine and sine waves of various frequencies and amplitudes.
In actual practice, however, many important time-variable functions cannot readily be converted to a Fourier series, equation 1, in the above-described manner. In other words, such functions have a repetition interval which is infinitely long. To resolve such functions into a series of sine and cosine terms of various frequencies, it is necessary to extend the period I over which the Fourier coefficients are calculated to infinity. Thus, equations 2, 3, and 4 become: ##EQU3## g(.omega.) is defined as the continuous Fourier transform of f(t). The signal f(t) may be obtained by the inverse transformation of (4A): ##EQU4## Equations (4A) and (4B) are referred to as Fourier transform pairs.
In addition to lacking periodicity, many time-variable functions are too complicated for the function, f(t), to be expressed in a manner enabling practical solution of the Euler formulas. More sophisticated techniques known as "discrete Fourier transformations" (DFT's) are, therefore, required to enable analysis of such complicated functions. By use of DFT techniques, a complicated time-variable function, S(t), is sampled at short time intervals so as to provide, at each sampling time, an amplitude reading, S.sub.n. Ordinarily, a set of "N" S.sub.n values, S.sub.0, S.sub.1, S.sub.2 . . . S.sub.N-1, are obtained for each signal "period" or time block of duration T, so that the sampling time interval is equal to T/N. A corresponding set of Fourier terms, f.sub.m, called the Fourier spectrum of the signal, is obtained from the set of S.sub.n data by application of the known DFT equation: ##EQU5## the [e.sup.-i2.pi./N ].sup.nm term is defined as the W.sup.MN term representing a series of sine and cosine terms, according to the relationship: EQU e.sup.i.omega.t =cos .omega.t+i sin .omega.t (6) EQU e.sup.-i.omega.t =cos .omega.t-i sin .omega.t (6a)
The [e.sup.-i2.pi./N ].sup.nm term in Equation (5) is also seen to represent a matrix and Equation (5) is thus usually expressed more conveniently as: ##EQU6## in which [W.sub.nm ] represents an N by N matrix. Fully written out in matrix form, Equation (7) becomes: ##EQU7##
Since from Equation (8), Wmn is seen to be an N by N matrix, N.sup.2 computations of the type Woo.multidot.So, W.sub.01 .multidot.S.sub.1, . . . W.sub.N-1 N-1. S.sub.N-1 are required to obtain the Fourier spectrum, fm. However, as many as 4N.sup.2 individual computations may actually be required, as both Wm.sub.n and Sn may be complex numbers of the form (a.+-.i b). When N is large, as is usually necessary to achieve a good resolution of the signal, S(t), the 4N.sup.2 number of computations will, of course, be very large. For example, when N is equal to 16,000, in excess of a billion computations may be required to obtain the Fourier spectrum for each signal block analyzed. If an associated computation rate of one million per second is assumed, over a quarter of an hour of computation time would be required. Computation times of such length are clearly unacceptable when substantially real-time signal analysis is required.
Because of the very large number of computations required to obtain the Fourier spectrum from matrix Equation (8), so-called "fast Fourier transform" (FFT) techniques have been developed which substantially reduce the number of computations, and thus the computation time, required to obtain a Fourier spectrum, f.sub.m. It has been shown, (for example, at page 144 of "Digital Signal Processing, Theory, Design and Implementation", by Peled and Liu, published by John Wiley and Sons, 1976), that the Wmn matrix can be reduced to a series of smaller matrices in a manner reducing the total number of computations from 4N.sup.2 to only N log.sub.2 N. Thus, for the exemplary N equal to 16,000, the number of computations is reduced to under 200,000. Computation times, at the assumed rate of a million computations per second, are accordingly reduced to only about 200 milliseconds. Such FFT techniques, and apparatus for implementing them, are obviously very important when substantially real-time signal analysis is needed.
Known FFT techniques effectively replace the Wmn matrix of Equation (8) by a series of ".alpha." smaller, sparse matrices, the number .alpha. being of obtained from the relationship: EQU N=2.sup..alpha., (9)
So that for the assumed N equal to about 16,000, .alpha. is equal to 14. Equation (8) is thereby reduced to the following expression: ##EQU8## As is well known, matrix operation of Equation (10) is performed serially from right to left; with each subsequent matrix operating on the previous matrix product.
Typically, and as described in greater detail below, each matrix operation of Equation (10) can be mathematically represented by a sequence of N/2 pairs of operations, termed "butterfly" operations because of their representational appearance. The Fourier spectrum is thus obtained through .alpha. sequences of N/2 pairs of butterfly operations.
These FFT butterfly operations can be made by various means; as an illustration, high speed, general purpose computers can be programmed to perform the required computations. However, special purpose FFT circuits, generally termed FFT's or FFT computers are preferred for the reason that FFT's are usually smaller and less expensive than general purpose computers of comparable FFT computational performance.
Because, in part, of the increased usage of FFT's and the continued advancement in the very large scale integration (VLSI) art, improvements over heretofore known FFT's are highly desirable. Additional reductions in FFT size and weight are important for many applications, such as aircraft, satellites and missiles. Comparable or improved FFT performance, but at lower cost, is also important to many applications, as is compatibility of the FFT to VLSI technology.
Therefore, an object of the present invention is to provide, for specified performance criteria, an FFT which is substantially smaller and/or cheaper than heretofore available FFT's.
An additional object of the present invention is to provide an FFT in which the clock timing schedule for receiving data required for the butterfly computations is independent of, or decoupled from, the clock timing schedule for performing the computations.
Other objects, features and advantages of the present invention will be readily apparent from the following detailed description thereof when taken in conjunction with the accompanying drawings.